package com.lw.leetcode.binary.b;

import java.io.BufferedReader;
import java.io.File;
import java.io.FileInputStream;
import java.io.InputStreamReader;
import java.util.Arrays;

/**
 * Created with IntelliJ IDEA.
 * 面试题 17.08. 马戏团人塔
 *
 * @author liw
 * @version 1.0
 * @date 2022/2/16 13:42
 */
public class BestSeqAtIndex {

    public static void main(String[] args) {
        BestSeqAtIndex test = new BestSeqAtIndex();

        // 6
//        int[] heights = {65,70,56,75,60,68};
//        int[] weights = {100,150,90,190,95,110};

        // 2
//        int[] heights = {100, 90, 90, 90, 80, 80};
//        int[] weights = {10, 150, 140, 120, 145, 143};

        // 5
//        int[] heights = {2868,5485,1356,1306,6017,8941,7535,4941,6331,6181};
//        int[] weights = {5042,3995,7985,1651,5991,7036,9391,428,7561,8594};

        // 5
        int[] heights = test.getArr("C:\\Users\\wang.li\\Desktop\\a.txt");
        int[] weights = test.getArr("C:\\Users\\wang.li\\Desktop\\b.txt");

        int index = test.bestSeqAtIndex3(heights, weights);
        System.out.println(index);
    }


    public int bestSeqAtIndex(int[] height, int[] weight) {
        int length = height.length;
        if (length < 2) {
            return length;
        }
        int[][] arr = new int[length][2];
        for (int i = 0; i < length; i++) {
            arr[i][0] = height[i];
            arr[i][1] = weight[i];
        }
        Arrays.sort(arr, (a, b) -> a[0] == b[0] ? Integer.compare(b[1], a[1]) : Integer.compare(a[0], b[0]));
        int[] items = new int[length];
        items[0] = arr[0][1];
        int index = 0;
        for (int i = 1; i < length; i++) {
            int b = arr[i][1];
            if (items[index] < b) {
                items[++index] = b;
            } else {
                items[binary(items, b, index)] = b;
            }
        }
        return index + 1;
    }

    public int binary(int[] nums, int target, int end) {
        if (nums[0] >= target) {
            return 0;
        }
        int st = 0;
        while (st < end) {
            int m = st + ((end - st + 1) >> 1);
            if (nums[m] < target) {
                st = m;
            } else {
                end = m - 1;
            }
        }
        return st + 1;
    }


    private int[] getArr(String path) {
        String s = readTxtFile(path);
        String[] split = s.split(",");
        int[] arr = new int[split.length];
        for (int i = 0; i < split.length; i++) {
            arr[i] = Integer.parseInt(split[i]);
        }
        return arr;
    }


    public static String readTxtFile(String filePath) {
        try {
            String encoding = "GBK";
            File file = new File(filePath);
            if (file.isFile() && file.exists()) { //判断文件是否存在
                InputStreamReader read = new InputStreamReader(
                        new FileInputStream(file), encoding);//考虑到编码格式
                BufferedReader bufferedReader = new BufferedReader(read);
                String lineTxt = null;
                StringBuilder sb = new StringBuilder();
                while ((lineTxt = bufferedReader.readLine()) != null) {
                    sb.append(lineTxt);
                }
                read.close();
                return sb.toString();
            } else {
                System.out.println("找不到指定的文件");
            }
        } catch (Exception e) {
            System.out.println("读取文件内容出错");
            e.printStackTrace();
        }

        return "";
    }


    /**
     * ************************一直不好用，先用别人的解体思路。。。
     *
     * @param height
     * @param weight
     * @return
     */
    public int bestSeqAtIndex3(int[] height, int[] weight) {
        int length = height.length;
        int[][] arr = new int[length][2];
        for (int i = 0; i < length; i++) {
            arr[i][0] = height[i];
            arr[i][1] = weight[i];
        }
        Arrays.sort(arr, (a, b) -> a[0] == b[0] ? Integer.compare(b[1], a[1]) : Integer.compare(b[0], a[0]));
        int[] items = new int[length];
        items[0] = arr[0][1];
        int last = arr[0][1];
        int index = 0;
        boolean addFlag = false;
        for (int i = 1; i < length; i++) {
            int a = arr[i][0];
            int b = arr[i][1];
            if ((a == arr[i - 1][0] && addFlag) || b == last) {
                continue;
            }
            if (a != arr[i - 1][0]) {
                last = items[index];
            }
            if (b < last) {
                addFlag = true;
                items[++index] = b;
            } else {
                addFlag = false;
                if (a == arr[i - 1][0] && b <= items[index]) {
                    continue;
                }
                binary3(items, b, index);
            }
        }
        return index + 1;
    }

    private void binary3(int[] nums, int target, int end) {
        if (nums[0] <= target) {
            nums[0] = target;
            return;
        }
        int st = 0;
        while (st < end) {
            int m = st + ((end - st + 1) >> 1);
            if (nums[m] > target) {
                st = m;
            } else {
                end = m - 1;
            }
        }
        nums[st + 1] = target;
    }

}
